/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

import java.util.function.Consumer;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.io.IOException;

/**
 * <p>哈希表和链表,实现了Map接口，具有可预测的迭代顺序。
 * 这个实现与HashMap的不同之处在于，它维护了一个双链表，该列表遍历其所有条目。
 * 这个链表定义了迭代顺序，它通常是键插入到映射中的顺序(插入顺序)。
 * 注意，如果一个键被重新插入到映射中，插入顺序不会受到影响。
 * (已经有key了，再put(key,value))。
 *
 * <p>这个实现使它的用户免于HashMap(和Hashtable)提供的未指定的、混乱的排序，
 * 也不会增加与TreeMap相关的成本。
 * 它可以用于生成与原始的map顺序相同的map副本，而不管原始map的实现:
 * <pre>
 *     void foo(Map m) {
 *         Map copy = new LinkedHashMap(m);
 *         ...
 *     }
 * </pre>
 * 如果一个功能先获取一个map作为输入，然后复制它，
 * 然后返回结果，其顺序由被复制的map的顺序决定，那么这种技术特别有用。
 * (客户一般都喜欢按照收到礼物的顺序来退货。)
 *
 * <p>提供了一个特殊的构造函数LinkedHashMap(int,float,boolean)，
 * 被提供来创建一个链接的散列映射，其迭代的顺序是其条目最后一次被访问的顺序，从最少被访问到最近被访问(访问顺序)。
 * 这种map非常适合构建LRU缓存。（Least Recently Used，最近最少使用）
 * 调用put、putIfAbsent、get、getOrDefault、compute、computeIfAbsent、computeIfPresent或merge方法将导致对相应项的访问(假设在调用完成后存在)。
 * 如果值被替换，则replace方法只会导致对条目的访问。
 * putAll方法为指定映射中的每个映射生成一个条目访问，其顺序是由指定map的entrySet迭代器提供键-值映射。
 * 没有其他方法生成条目访问。特别是，对集合视图的操作不会影响依赖的map的迭代顺序。
 *
 * <p>可以重写removeEldestEntry(map. entry)方法，以便在向映射添加新映射时自动删除陈旧的映射。
 *
 * <p>该类提供所有可选的映射操作，并允许空元素。
 * 与HashMap一样，它为基本操作(添加、包含和删除)提供了固定时间的性能，假设散列函数正确地将元素分散到各个bucket中。
 * 由于维护链表的额外开销，性能可能略低于HashMap，但有一个例外:
 * 对LinkedHashMap的集合视图的迭代需要与映射的大小成比例的时间，而与它的容量无关。
 * HashMap的迭代可能更昂贵，需要的时间与它的容量成比例。
 *
 * <p>一个链接的哈希映射有两个影响其性能的参数:初始容量和负载因子。
 * 它们被精确地定义为HashMap。
 * 但是，请注意，对于初始容量选择过高值的惩罚对于这个类来说没有HashMap那么严重，因为这个类的迭代时间不受容量的影响。
 *
 * <p>注意，这个实现不是同步的。如果多个线程同时访问一个链接的散列映射，并且至少有一个线程从结构上修改了该映射，则必须在外部对其进行同步。
 * 这通常是通过对一些自然封装了映射的对象进行同步来实现的。
 * 如果不存在这样的对象，则应该使用Collections.synchronizedMap方法。这最好在创建时完成，以防止意外的不同步访问map:<pre>
 *   Map m = Collections.synchronizedMap(new LinkedHashMap(...));</pre>
 *
 * 结构修改是添加或删除一个或多个映射的任何操作，对于基于访问顺序的链接哈希映射，它会影响迭代顺序。
 * 在基于插入顺序的链接哈希映射中，仅更改已包含在映射中的键相关联的值不是结构性修改。
 * 在基于访问顺序的链接哈希映射中，仅使用get查询映射是一种结构修改。
 * 即对于基于插入顺序的，add，remove影响。
 * 基于访问顺序的，add，remove，get都影响。
 *
 * <p>这个类的集合视图，返回的迭代器是快速失败:
 * 如果创建迭代器后修改map的结构,除非通过迭代器的删除方法,迭代器将抛出ConcurrentModificationException。
 * 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在将来某个不确定的时间冒任意的、不确定的行为的风险。
 *
 * <p>注意，不能保证迭代器的快速故障行为，因为通常来说，在存在非同步并发修改的情况下，不可能做出任何严格的保证。
 * 故障快速迭代器在最大努力的基础上抛出ConcurrentModificationException。
 * 因此，编写一个依赖于这个异常的正确性的程序是错误的:迭代器的快速故障行为应该只用于检测bug。
 *
 * <p>这个类的所有集合视图方法返回的集合的spliterator方法返回的spliterator是迟绑定的、快速失败的，另外还报告ORDERED。
 * 
 * 这个类的所有集合视图方法返回的集合的spliterator方法返回的spliterator是从相应集合的迭代器创建的。
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author  Josh Bloch
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     HashMap
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.4
 */
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    /*
     * 实现注释。这个类以前的版本在内部结构上略有不同。
     * 因为超类HashMap现在对它的一些节点使用树节点。
     * 类LinkedHashMap.Entry现在被视为中间节点类，也可以将其转换为树形式。
     * 这个类的名字，LinkedHashMap.Entry，在当前的上下文中，在几个方面令人困惑，但是不能更改。
     * 否则，即使它没有导出到这个包之外，已知的一些现有源代码在调用removeEldestEntry时依赖于符号的解析规则，
     * 该规则抑制了由于含糊不清的用法而导致的编译错误。因此，我们保留这个名称以保持未修改的编译性。
     *
     * 节点类中的更改还需要使用两个字段(head和tail)
     * 而不是指向头节点的指针来维护双链接的before/after列表。
     * 这个类以前还使用了不同风格的回调方法在访问，插入和删除。
     */

    /**
     * HashMap.Node 的子类，应用于普通的 LinkedHashMap 的节点。
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
    	// node有 key，value， hash，next
    	// linkedlist的entry，增加了before，after
    	// TreeNode增加了 parent,left,right,prev,red
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * 双端队列的头结点（最老的节点）
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 双端队列的尾结点（最新的节点）
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * 这个链接的哈希映射的迭代顺序:对于访问顺序为true，对于插入顺序为false。
     * 默认为false，插入顺序。
     * @serial
     */
    final boolean accessOrder;

    // 内部工具方法

    // 设置双端队列的尾部为p
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

    // 就是dst替换src的链接关系，原来b  src  a 变成  b  dst  a
    // 调用replacementNode和replacementTreeNode时调用这个方法
    // 普通节点与树节点转换时，调用
    private void transferLinks(LinkedHashMap.Entry<K,V> src,
                               LinkedHashMap.Entry<K,V> dst) {
    	// 设置src的before，after给dst，现在是b  dst   a
        LinkedHashMap.Entry<K,V> b = dst.before = src.before;
        LinkedHashMap.Entry<K,V> a = dst.after = src.after;
        // 设置a，b，head，tail节点
        if (b == null)
            head = dst;
        else
            b.after = dst;
        if (a == null)
            tail = dst;
        else
            a.before = dst;
    }

    // overrides of HashMap hook methods

    void reinitialize() {
        super.reinitialize();
        // 设置head和tail
        head = tail = null;
    }

    // hashmap的putVal方法，最后如果不是新增节点，而是对已经存在节点进行修改，调用afterNodeAccess
    // 如果是新增节点，会调用linkedhashmap的newNode方法，里面将新增节点放到队列尾部
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        // 设置双端队列的尾部为p
        linkNodeLast(p);
        return p;
    }

    Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        LinkedHashMap.Entry<K,V> t =
            new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);
        return t;
    }

    // hashmap的removeNode方法，最后调用afterNodeRemoval(node)
    void afterNodeRemoval(Node<K,V> e) { // 删除链接
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 顺序 b  p  a
        // 设置p的before和after
        p.before = p.after = null;
        // 设置head或者b的after
        if (b == null)
            head = a;
        else
            b.after = a;
        // 设置tail或者a的before
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

    // hashmap的putVal方法在最后，调用afterNodeInsertion(evict);
    // evict 如果false，哈希表处于创建阶段。
    void afterNodeInsertion(boolean evict) { // 可能删除最老元素
        LinkedHashMap.Entry<K,V> first;
        // 如果不是创建阶段，head不为null，removeEldestEntry返回true，删除first（LinkedHashMap不删除）
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

    // hashmap的putVal方法，最后如果不是新增节点，而是对已经存在节点进行修改，调用afterNodeAccess
    // 如果是新增节点，会调用linkedhashmap的newNode方法，里面将新增节点放到队列尾部
    // linkedhashmap的get方法，最后如果为访问顺序，调用afterNodeAccess
    void afterNodeAccess(Node<K,V> e) { // 将节点移动到最后
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
        	// 如果是访问顺序，而且tail不是e
        	// 赋值tail给last，e给p
        	// b和a是p的before和after
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            // 设置p的after
            p.after = null;
            // 设置head或者b的after
            if (b == null)
                head = a;
            else
                b.after = a;
            // 设置a的before
            if (a != null)
                a.before = b;
            else
            	// 如果a为null，设置last为b
                last = b;
            // 设置head或者p的before和last的after
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            // 设置tail
            tail = p;
            ++modCount;
        }
    }

    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        	// 从head开始循环
            s.writeObject(e.key);
            s.writeObject(e.value);
        }
    }

    /**
     * 使用指定的初始容量和负载因子构造一个按插入顺序排列的空LinkedHashMap实例。
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
    	// 调用hashmap的方法
        super(initialCapacity, loadFactor);
        // 默认为false，插入顺序
        accessOrder = false;
    }

    /**
     * C使用指定的初始容量和默认的负载因子(0.75)构造一个按插入顺序排列的空LinkedHashMap实例。
     *
     * @param  initialCapacity the initial capacity
     * @throws IllegalArgumentException if the initial capacity is negative
     */
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    /**
     * 使用默认初始容量(16)和负载因子(0.75)构造一个按插入顺序排列的空LinkedHashMap实例。
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    /**
     * 使用与指定映射相同的映射，构造按插入顺序排列的LinkedHashMap实例。
     * LinkedHashMap实例是使用默认的负载因子(0.75)和足够容纳指定映射的初始容量创建的。
     *
     * @param  m the map whose mappings are to be placed in this map
     * @throws NullPointerException if the specified map is null
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    /**
     * 使用指定的初始容量、负载因子和排序模式构造一个空的LinkedHashMap实例。
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }


    /**
     * 如果此映射将一个或多个键映射到指定的值，则返回true。
     *
     * @param value value whose presence in this map is to be tested
     * @return <tt>true</tt> if this map maps one or more keys to the
     *         specified value
     */
    public boolean containsValue(Object value) {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        	// 从head开始，不断e = e.after循环
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        return false;
    }

    /**
     * 返回指定键映射到的值，如果该映射不包含键的映射，则返回null。
     *
     * <p>更正式地说，如果这个映射包含一个从键k到值v的映射(key==null ?k==null: key.equals(k))，
     * 则该方法返回v;否则返回null。(最多可以有一个这样的映射。)
     *
     * <p>返回值为null并不一定表示映射不包含键的映射;映射也可能显式地将键映射为null。
     * containsKey操作可以用来区分这两种情况。
     * 
     * 
     */
    public V get(Object key) {
        Node<K,V> e;
        // 先调用hashmap的getNode方法
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
        	// 如果为访问顺序，调用afterNodeAccess
            afterNodeAccess(e);
        return e.value;
    }

    /**
     * {@inheritDoc}
     */
    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;
       if (accessOrder)
           afterNodeAccess(e);
       return e.value;
   }

    /**
     * {@inheritDoc}
     */
    public void clear() {
        super.clear();
        // head和tail为null
        head = tail = null;
    }

    /**
     * 如果此map应该删除其最老的条目，则返回true。
     * 在向映射中插入新条目之后，put和putAll将调用此方法。
     * 它为实现者提供了在每次添加新条目时删除最老条目的机会。
     * 如果映射表示一个缓存，这是很有用的:它允许映射通过删除陈旧的条目来减少内存消耗。
     *
     * <p>示例使用:这个覆盖将允许映射增长到100个条目，
     * 然后在每次添加新条目时删除最老的条目，从而保持100个条目的稳定状态。
     * <pre>
     *     private static final int MAX_ENTRIES = 100;
     *
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *        return size() &gt; MAX_ENTRIES;
     *     }
     * </pre>
     *
     * <p>此方法通常不以任何方式修改映射，而是允许映射根据其返回值的方向修改自身。
     * （即 if(removeEldestEntry(eldest)) remove(eldest)  )
     * 允许此方法直接修改映射，但如果这样做，则必须返回false(指示映射不应尝试任何进一步修改)。
     * 在此方法中修改映射后返回true的效果是未指定的。
     *
     * <p>这个实现只返回false(因此这个映射就像一个普通的映射——最年长的元素永远不会被删除)。
     *
     * @param    eldest The least recently inserted entry in the map, or if
     *           this is an access-ordered map, the least recently accessed
     *           entry.  This is the entry that will be removed it this
     *           method returns <tt>true</tt>.  If the map was empty prior
     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
     *           in this invocation, this will be the entry that was just
     *           inserted; in other words, if the map contains a single
     *           entry, the eldest entry is also the newest.
     * @return   <tt>true</tt> if the eldest entry should be removed
     *           from the map; <tt>false</tt> if it should be retained.
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

    /**
     * Returns a {@link Set} view of the keys contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own <tt>remove</tt> operation), the results of
     * the iteration are undefined.  The set supports element removal,
     * which removes the corresponding mapping from the map, via the
     * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
     * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
     * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
     * operations.
     * Its {@link Spliterator} typically provides faster sequential
     * performance but much poorer parallel performance than that of
     * {@code HashMap}.
     *
     * @return a set view of the keys contained in this map
     */
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new LinkedKeySet();
            keySet = ks;
        }
        return ks;
    }

    final class LinkedKeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        public final Iterator<K> iterator() {
            return new LinkedKeyIterator();
        }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator()  {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED |
                                            Spliterator.DISTINCT);
        }
        public final void forEach(Consumer<? super K> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            	// 从head开始循环
                action.accept(e.key);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * Returns a {@link Collection} view of the values contained in this map.
     * The collection is backed by the map, so changes to the map are
     * reflected in the collection, and vice-versa.  If the map is
     * modified while an iteration over the collection is in progress
     * (except through the iterator's own <tt>remove</tt> operation),
     * the results of the iteration are undefined.  The collection
     * supports element removal, which removes the corresponding
     * mapping from the map, via the <tt>Iterator.remove</tt>,
     * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
     * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
     * support the <tt>add</tt> or <tt>addAll</tt> operations.
     * Its {@link Spliterator} typically provides faster sequential
     * performance but much poorer parallel performance than that of
     * {@code HashMap}.
     *
     * @return a view of the values contained in this map
     */
    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new LinkedValues();
            values = vs;
        }
        return vs;
    }

    final class LinkedValues extends AbstractCollection<V> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        public final Iterator<V> iterator() {
            return new LinkedValueIterator();
        }
        public final boolean contains(Object o) { return containsValue(o); }
        public final Spliterator<V> spliterator() {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED);
        }
        public final void forEach(Consumer<? super V> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                action.accept(e.value);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    /**
     * Returns a {@link Set} view of the mappings contained in this map.
     * The set is backed by the map, so changes to the map are
     * reflected in the set, and vice-versa.  If the map is modified
     * while an iteration over the set is in progress (except through
     * the iterator's own <tt>remove</tt> operation, or through the
     * <tt>setValue</tt> operation on a map entry returned by the
     * iterator) the results of the iteration are undefined.  The set
     * supports element removal, which removes the corresponding
     * mapping from the map, via the <tt>Iterator.remove</tt>,
     * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
     * <tt>clear</tt> operations.  It does not support the
     * <tt>add</tt> or <tt>addAll</tt> operations.
     * Its {@link Spliterator} typically provides faster sequential
     * performance but much poorer parallel performance than that of
     * {@code HashMap}.
     *
     * @return a set view of the mappings contained in this map
     */
    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }

    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED |
                                            Spliterator.DISTINCT);
        }
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                action.accept(e);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

    // Map overrides

    public void forEach(BiConsumer<? super K, ? super V> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }

    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
        if (function == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            e.value = function.apply(e.key, e.value);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }

    // Iterators

    abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;

        LinkedHashIterator() {
        	// next最初为head
            next = head;
            expectedModCount = modCount;
            current = null;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            current = e;
            // 递归时，next=next.after
            next = e.after;
            return e;
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

    // 下面与hashmap的一样，基于nextNode方法
    final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().getKey(); }
    }

    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }


}
